#pragma once
#include<iostream>
#include<string>

using namespace std;

//冒泡排序
void BubbleSort(int * array,int length)
{
    int count = 0;
    for(int i=0;i<length;i++)
    {
        for(int j=0;j<length-1;j++)
        {
            count ++;
            if(array[j]>array[j+1])
            {
                swap(array[j],array[j+1]);
            }
        }
    }
}

//插入排序
void InsertionSort(int * array,int length)
{
    for(int i=0;i<length;i++)
    {
        int temp = array[i];
        int key = i;
        for(int j=i;j>0;j--)
        {
            if(array[j]<array[j-1])
            {
                swap(array[j],array[j-1]);
            }
            
        }
        

    }
}

//选择排序
void SelectionSort(int * array,int length)
{
    for(int i=0;i<length;i++)
    {
        int min = i;
        for(int j=i;j<length;j++)
        {
            if(array[min]>array[j])
            {
                min = j;
            }
        }
        swap(array[i],array[min]);
    }
}

//桶排序
void BucketSort(int * array,int length)
{
    int max = array[0];
    for(int i=1;i<length;i++)
    {
        max = max > array[i] ? max : array[i];
    }
    int * temp = new int[max+1];
    for(int i=0;i<=max;i++)
    {
        temp[i] = 0;
    }

    for(int i=0;i<length;i++)
    {
        temp[array[i]]++;
    }

    int count=0;
    for(int i=0;i<=max;i++)
    {
        while(temp[i]!=0)
        {
            array[count] = i;
            temp[i]--;
            count++;
        }
    }
    delete[] temp;
}

//快速排序
void FastSort(int * array,int left,int right)
{
    
    if (left >= right)
    {
    return;
    }

    swap(array[left], array[(left + right) / 2]);
    int i = left, j = right, k = array[left];
    while (i < j)
    {
        while (array[j] > k && i < j)
        {
            j--;
        }
        array[i++] = array[j];
        while (array[i] < k && i < j)
        {
            i++;
        }
        array[j--] = array[i];
    }
    array[(i+j+1)/2] = k;
    FastSort(array,left, (i+j+1)/2-1);
    FastSort(array,(i+j+1)/2+1, right);
    
}


//基数排序
void RadixSort(int * array,int length)
{
    int max = array[0];
    for (int i = 1; i < length; i++)
    {
        if (array[i] > max)
        {
            max = array[i];
        }
    }
    int d = 0;
    while( max > 0 ) {
        max /= 10;
        d ++;
    }
 
    int *tmp = new int[length];
    int *count = new int[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < length; j++)
        {
            k = (array[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = length - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (array[j] / radix) % 10;
            tmp[count[k] - 1] = array[j];
            count[k]--;
        }
        for(j = 0; j < length; j++) //将临时数组的内容复制到data中
            array[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}

//希尔排序
void ShellSort(int * array,int length)
{
    for(int gap=length/2;gap>0;gap/=2)
    {
                // 直接插入排序
        for(int i=gap;i<length;++i)
        {
            int j=i;
            while(j-gap>=0 && array[j-gap]>array[j])
            {
                array[j-gap] = array[j-gap]+array[j];
                array[j]     = array[j-gap]-array[j];
                array[j-gap] = array[j-gap]-array[j];
                j=j-gap;
            }
        }
    }
}

//计数排序
void CountingSort(int * array,int length)
{
    int * temp = new int[length];
    int now;
    int count;
    for(int i=0;i<length;i++)
    {
        now = array[i];
        count = 0;
        for(int j=0;j<length;j++)
        {
            if(now>array[j])
            {
                count++;
            }
        }
        temp[count] = now;
    }
    for(int i=0;i<length;i++)
    {
        array[i] = temp[i];
    }
    delete[] temp;
}